In recent years, there has been an explosive growth in demand for wireless data services, and the evolution from wireless voice to wireless data is causing exponentially increasing demand for wireless capacity. With already more than one billion subscribers worldwide, subscription to wireless services is expected to exceed those of wire-line services by the year 2005. This has forced wireless service providers and equipment vendors to look into ways of increasing the data rates of wireless systems and has motivated an enormous body of research.
The wireless channel suffers from many artifacts such as path loss, shadowing, fading, noise, limited bandwidth, power limitation at the mobile terminal, and interference from other users. These limitations cause the wireless channel to resemble a narrow pipe that does not allow rapid flow of data and make the design of bandwidth efficient high data rate wireless communications a challenging task. Further challenges in wireless system design include the design of resource allocation, mobility issues related to rapidly changing physical channels, portability, and providing privacy and security.
When the transmission channel is experiencing deep fades, it is impossible for the receiver to determine the transmitted signal unless another replica or version of the signal is also sent to the receiver. This resource is called diversity, and is one of the most important single contributors to reliable transmission over wireless channels. Examples of diversity include:                1. Temporal Diversity: Replicas of the transmitted signal are provided to the receiver in the form of redundancy in the temporal domain.        2. Frequency Diversity: The fact that waves transmitted on different frequencies induce different multipath structure in the propagation media is exploited. Replicas of the transmitted signal are provided to the receiver in the form of redundancy in the frequency domain.        3. Spatial Diversity: Spatially separated or differently polarized antennas are used. Replicas of the transmitted signal are provided to the receiver in the form of redundancy in the spatial domain. This can be provided with no penalty in bandwidth efficiency.        
Spatial diversity is typically a function of the number and placement of transmit and receive antennas relative to a transmitter and receiver. Systems employing spatial diversity with multiple transmit and receive antennas are generally referred to as multiple-input multiple-output (MIMO) systems. Accordingly, a transmitting device will have N transmit antennas, and the receiving device will have M receive antennas. Space-time coding controls what data is transmitted from each of the N transmit antennas. A space-time encoding function at the transmitter processes data to be transmitted and creates unique information to transmit from the N transmit antennas. Each of the M receive antennas will receive signals transmitted from each of the N transmit antennas. A space-time decoding function at the receiving device will combine the information sent from the N transmit antennas to recover the data.
Space-time coding (STC) is typically implemented using one of many techniques. One exemplary technique encodes the same data in different formats for transmission from the different transmit antennas. Thus, the same data is transmitted in different formats from each of the N transmit antennas. Another exemplary technique transmits different data from different ones of the N transmit antennas wherein the redundancy of the first technique is avoided. The first technique, space-time transmit diversity (STTD), is effective in maximizing diversity but inefficient due to the requisite redundancy. The second technique, which is often referred to as V-BLAST (Vertical-Bell Laboratories Layered Space Time), increases system throughput for systems having sufficient diversity available. Once a threshold amount of diversity is achieved, data rates increase linearly with the number of transmit and receive antennas for BLAST systems, whereas additional spatial diversity has little impact on data rates in STTD systems. Those skilled in the art will recognize other STC techniques such as space-time trellis codes and space-time block codes. Further information related to STTD and BLAST can be found in Siavash M. Alamouti, “A Simple Transmit Diversity Technique for Wireless Communications,” IEEE J. Select. Areas Commun., vol. 16, pp. 1451-1458, October 1998; G. J. Foschini, “Layered Space-time Architecture for Wireless Communications in a Fading Environment when Using Multi-element antennas,” Bell Labs Tech. J., pp. 41-59, Autumn 1996; G. D. Golden, G. J. Foschini, R. A. Valenzuela, and P. W. Wolniansky, “Detection Algorithm and Initial Laboratory Results Using V-BLAST Space-time Communication Architecture,” Electronics Letters, vol. 35, pp. 14-16, Jan. 1999; P. W. Wolniansky, G. J., Foschini, G. D. Golden, and R. A. Valenzuela, “V-BLAST: An Architecture for Realizing Very High Data Rates Over the Rich-scattering Wireless Channel,” Proc. IEEE ISSSE-98, Pisa, Italy, September 1998, pp. 295-300; V. Tarokh, et al., “Space-Time Codes for High Data Rate Wireless Communication: Performance Analysis and Code Construction,” IEEE Trans. Inform. Theory, pp. 744-765, March 1998; and Eko N. Onggosanusi, et al., “High Rate Space-time Block Coded Scheme: Performance and Improvement in Correlated Fading Channels,” IEEE Wireless Communications and Networking Conference, pp. 194-256, Orlando, Fla, USA, Mar. 17-21, 2002, which are incorporated herein by reference.
When there are N transmit and M receive antennas, for each transmission slot, N signals are transmitted at the same time from different transmit antennas. These signals have the same transmission period. Signals transmitted from different antennas undergo independent fades. The received signal at each receive antenna is a linear superposition of the transmitted signals perturbed by noise.
Mathematically speaking, if st,n is transmitted from antenna n, the signal rt,m received at antenna m is given by:
                              r                      t            ,            m                          =                                            ∑                              n                =                1                            N                        ⁢                                                  ⁢                                          α                                  n                  ,                  m                                            ⁢                              s                                  t                  ,                  n                                                              +                                    η              m                        .                                              Eq        .                                  ⁢        1            
The path gain αn,m is the path gain from transmit antenna n to receive antenna m, and ηm represents a noise variable. For flat fading, assume that the path gains are constant over a frame and vary from one frame to another.
Under this assumption, criteria for the design of space-time codes can be derived. To describe this criteria, any code word S is written as the space-time matrix:
                    S        =                              (                                                                                s                                          1                      ,                      1                                                                                                            s                                          1                      ,                      2                                                                                                            s                                          1                      ,                      3                                                                                        …                                                  …                                                                      s                                          1                      ,                      N                                                                                                                                        s                                          2                      ,                      1                                                                                                            s                                          2                      ,                      2                                                                                                            s                                          2                      ,                      3                                                                                        …                                                  …                                                                      s                                          2                      ,                      N                                                                                                                    ⋮                                                  ⋮                                                  ⋰                                                  ⋰                                                  ⋰                                                  ⋮                                                                                                  s                                          L                      ,                      1                                                                                                            s                                          L                      ,                      2                                                                                                            s                                          2                      ,                      3                                                                                        …                                                  …                                                                      s                                          L                      ,                      N                                                                                            )                    .                                    Eq        .                                  ⁢        2            To send code word S, at time t=1,2, . . . , L, the symbols st,1, st,2, . . . , st,N are sent simultaneously from transmit antennas 1,2, . . . , N, respectively. The design criteria for space-time codes require that for any two code words C1≠C2, the error matrix C1-C2 has to be full rank in order to obtain diversity NM, and the determinant of (C1-C2)*(C1-C2) is large. Two exemplary space-time codes, space-time block and trellis codes, are provided.
For simplicity, assume that there are two transmit antennas (N=2) and M receive antennas. Consider a signal constellation with 2b elements, such as BPSK, QPSK, 8-PSK, 16-QAM. At time one, 2b bits arrive at the encoder and pick up constellation symbols s1 and s2. The transmission matrix is then:
                    S        =                              (                                                                                s                    1                                                                                        s                    2                                                                                                                    -                                          s                      2                      *                                                                                                            s                    1                    *                                                                        )                    .                                    Eq        .                                  ⁢        3            This is the so-called Alamouti scheme, and is an example of a space-time block code. Maximum likelihood decoding (MLD) of the above code amounts to minimizing the decision metric:
                              ∑                      m            =            1                    M                ⁢                                  ⁢                  (                                                                                                          r                                          1                      ,                      m                                                        -                                                            α                                              1                        ,                        m                                                              ⁢                                          s                      1                                                        -                                                            α                                              2                        ,                        m                                                              ⁢                                          s                      2                                                                                                  2                        +                                                                                                r                                          2                      ,                      m                                                        +                                                            α                                              1                        ,                        m                                                              ⁢                                          s                      2                      *                                                        -                                                            α                                              2                        ,                        m                                                              ⁢                                          s                      1                      *                                                                                                  2                                )                                    Eq        .                                  ⁢        4            over all possible values of s1 and s2. It can be shown that the above metric decomposes into two parts, one of which:
                                          -                                          ∑                                  m                  =                  1                                M                            ⁢                                                          ⁢                              [                                                                            r                                              1                        ,                        m                                                              ⁢                                          α                                              1                        ,                        m                                            *                                        ⁢                                          s                      1                      *                                                        +                                                            r                                              1                        ,                        m                                            *                                        ⁢                                          α                                              1                        ,                        m                                                              ⁢                                          s                      1                                                        +                                                            r                                              2                        ,                        m                                                              ⁢                                          α                                              2                        ,                        m                                            *                                        ⁢                                          s                      1                                                        +                                                            r                                              2                        ,                        m                                            *                                        ⁢                                          α                                              2                        ,                        m                                                              ⁢                                          s                      1                      *                                                                      ]                                              +                                                                                      s                  1                                                            2                        ⁢                                          ∑                                  m                  =                  1                                M                            ⁢                                                          ⁢                                                ∑                                      n                    =                    1                                    2                                ⁢                                                                                                α                                              n                        ,                        m                                                                                                  2                                                                    ,                            Eq        .                                  ⁢        5            is only a function of s1, and the other one:
                                          -                                          ∑                                  m                  =                  1                                M                            ⁢                                                          ⁢                              [                                                                            r                                              1                        ,                        m                                                              ⁢                                          α                                              2                        ,                        m                                            *                                        ⁢                                          s                      2                      *                                                        +                                                            r                                              1                        ,                        m                                            *                                        ⁢                                          α                                              2                        ,                        m                                                              ⁢                                          s                      2                                                        -                                                            r                                              2                        ,                        m                                                              ⁢                                          α                                              1                        ,                        m                                            *                                        ⁢                                          s                      2                                                        -                                                            r                                              2                        ,                        m                                            *                                        ⁢                                          α                                              1                        ,                        m                                                              ⁢                                          s                      2                      *                                                                      ]                                              +                                                    [                                  s                  2                                ]                            2                        ⁢                                          ∑                                  m                  =                  1                                M                            ⁢                                                          ⁢                                                ∑                                      n                    =                    1                                    2                                ⁢                                                                                                α                                              n                        ,                        m                                                                                                  2                                                                    ,                            Eq        .                                  ⁢        6            is only a function of s2. Thus, to decode s1 and s2, respectively, the decoder minimizes the first and the second part of the above metric over all constellation symbols separately. These metrics are equivalent to:
                                                                                    [                                                      ∑                                          m                      =                      1                                        M                                    ⁢                                                                          ⁢                                      (                                                                                            r                                                      1                            ,                            m                                                                          ⁢                                                  α                                                      1                            ,                            m                                                    *                                                                    +                                                                        r                                                      2                            ,                            m                                                    *                                                ⁢                                                  α                                                      2                            ,                            m                                                                                                                )                                                  ]                            -                              s                1                                                          2                +                              (                                          -                1                            +                                                ∑                                      m                    =                    1                                    M                                ⁢                                                                  ⁢                                                      ∑                                          n                      =                      1                                        2                                    ⁢                                                                                                          α                                                  n                          ,                          m                                                                                                            2                                                                        )                    ⁢                                                                  s                1                                                    2                                              Eq        .                                  ⁢        7            for decoding s1 and
                                                                    [                                                                    ∑                                          m                      =                      1                                        M                                    ⁢                                                                          ⁢                                      (                                                                                            r                                                      1                            ,                            m                                                                          ⁢                                                  α                                                      2                            ,                            m                                                    *                                                                    -                                                                        r                                                      2                            ,                            m                                                    *                                                ⁢                                                  α                                                      1                            ,                            m                                                                                                                )                                                  -                                  s                  2                                            ]                                            2                +                              (                                          -                1                            +                                                ∑                                      m                    =                    1                                    M                                ⁢                                                                  ⁢                                                      ∑                                          n                      =                      1                                        2                                    ⁢                                                                                                          α                                                  n                          ,                          m                                                                                                            2                                                                        )                    ⁢                                                                  s                2                                                    2                                              Eq        .                                  ⁢        8            for decoding s2. Thus, space-time block coding can be implemented using a very simple encoding/decoding algorithm, and achieves full spatial diversity. Trellis codes can also be designed using the space-time design criteria for BPSK, QPSK and 8-PSK, 16-QAM constellations.
The encoding typically starts at the zero state. Inductively, suppose that at time t, the encoder is at state St. At this time, two bits arrive at the encoder, and choose one of four branches originating from St. Two labels of that branch are sent from transmit antennas 1 and 2 simultaneously. Subsequently, the encoder moves to the state St+1 at the end of the chosen branch. The decoding of space-time trellis codes can be done using the Viterbi algorithm and it can be shown that this approach provides a 2M level diversity using the above code and M receive antennas.
An approach to increasing the aggregate throughput in wireless data packet networks is to use incremental redundancy. In this approach, the transmitter starts transmitting packets to the receiver with high bandwidth efficiency. If the received data is decoded correctly and this is acknowledged by the transmitter, then no additional action is needed by the transmitter. In the event that a data packet is not correctly received by the receiver, the transmitter sends additional symbols, all or some of which may be redundancy symbols. While these symbols decrease the overall bandwidth efficiency for the transmission of the packet data, they improve the reception. By combining the received words corresponding to these symbols and those of the original packet transmission, additional diversity, coding gain when redundant parity symbols are transmitted, signal energy, or a combination thereof are provided to the receiver, which can be used to correctly decode the transmitted data.
Various types of protocols exist that allow the receiver to inform the transmitter that certain packets were either not received or were corrupted. In response to an indication that a packet was corrupted, the transmitter will retransmit the corrupted packet. Certain communication systems implement an automatic repeat request (ARQ) protocol to provide error control. In general, ARQ-based systems will transmit an acknowledgement (ACK) from the receiver to the transmitter for each packet that is properly received, and send a negative-acknowledgement (NAK) when the receiver is unable to properly recover a packet. Incremental redundancy and ARQ techniques have been studied by those skilled in the art, and there is a vast body of existing literature on these topics. However, for transmission using multiple antennas, incremental redundancy schemes are not known. This is partially due to the fact that in a space-time channel, signals transmitted from different antennas superpose, and this makes it difficult to improve the transmitted signals with increasing redundancy. In this light, there is a need for a way to construct space-time codes to facilitate incremental redundancy in a spatially diverse communication environment.